package com.chenken.linkedlist;

import java.util.Stack;

/**
 * 反转单向链表
 * @author ken.chen
 *	给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *	https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/
 */
public class ReversalLinkedList {
	
	/**
	 * Definition for singly-linked list.
	 */
	 public class ListNode {
	      int val;
	      ListNode next;
	      ListNode() {}
	      ListNode(int val) { 
	    	  this.val = val; 
	      }
	      ListNode(int val, ListNode next) { 
	    	  this.val = val; 
	    	  this.next = next; 
	      }
	  }
	 
	 /**
	  * 递归
	  * @param head
	  * @return
	  */
	 public static ListNode reverseList(ListNode head) {
		 if(head	==	null || head.next == null) {
			 return null;
		 }
		 ListNode newHead = reverseList(head.next);
		 head.next.next = head;
		 head.next = null;
		 return newHead;
	}
	 
	 /**
	  * 使用栈
	  * @param head
	  * @return
	  */
	 public static ListNode reverseList2(ListNode head) {
		 //	将链表节点全部放入栈
		 Stack<ListNode> stack = new Stack<ListNode>();
		 while(head!=null) {
			 stack.push(head);
			 head = head.next;
		 }
		 if(stack.isEmpty()) {
			 return null;
		 }
		 ListNode node = stack.pop();
		 //	备份新的头结点
		 ListNode newHead = node;
		 while(!stack.isEmpty()) {
			 ListNode tempNode  = stack.pop();
			 node.next = tempNode;
			 node = node.next;
		 }
		 //	最后一个节点
		 node.next = null;
		 return newHead;
	}
	 
	 /**
	  * 使用双指针
	  * @param head
	  * @return
	  */
	 public static ListNode reverseList3(ListNode head) {
		 if(head == null || head.next == null) {
			 return head;
		 }
		 ListNode preNode = null;
		 ListNode iter = head;
		 while (iter != null) {
			 head = iter;//	备份head
			 iter = iter.next;	//	之前header的next指向header
			 iter.next = preNode;	//head的next指向null
			 preNode = head;	//	将preNode指向head
		 }
		 return preNode;
	 }
	
}
